package tree.leetcode_112_easy;

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        Queue<TreeNode> node = new LinkedList<>();
        Queue<Integer> valQueue = new LinkedList<>();
        node.offer(root);
        valQueue.offer(root.val);
        while(!node.isEmpty()){
            TreeNode cur = node.poll();
            int val = valQueue.poll();
            if(cur.left == null && cur.right == null && sum == val){
                return true;
            }
            if(cur.left != null){
                node.offer(cur.left);
                valQueue.offer(cur.left.val + val);
            }
            if(cur.right != null){
                node.offer(cur.right);
                valQueue.offer(cur.right.val + val);
            }
        }
        return false;
    }
}
